package kMesh;

import kGeom.*;

/**
 * @author ksteinfe a weighted graph class
 */
public class kGraph extends kElement {
	/**
	 * a the node points contained in a point cloud
	 */
	public kPointCloud nodes;
	/**
	 * an array of edges. each edge lists indices from verts
	 */
	public kGraphEdge[] edges;

	public kGraph() {
		nodes = new kPointCloud();
		edges = new kGraphEdge[0];
	}

	/*
	 * GET AND SET
	 * 
	 * 
	 * 
	 */

	public int appendNode(kVec node) {
		return nodes.append(node);
	}

	/**
	 * appends a given kGraphEdge to this graph, and returns the index of this new edge
	 * if this edge already exists, the weight of this new edge is added to the existing edge
	 * @param e
	 * the kGraphEdge to add
	 */
	public int appendEdge(kGraphEdge e) {
		if (e.isValid) {
			int index = indexOfExistingEdge(e);
			if (index >= 0) {
				edges[index].gainWeight(e.w);
				return index;
			} else {
				kGraphEdge[] temp = this.edges;
				this.edges = new kGraphEdge[this.edges.length + 1];
				for (int i = 0; i < temp.length; i++) {
					this.edges[i] = temp[i];
				}
				this.edges[this.edges.length - 1] = e;
				return this.edges.length - 1;
			}
		}
		//System.out.println("!!! kGraph.appendEdge() trying to append an invalid edge");
		return -1;
	}
	
	/**
	 * appends a given kLine to this graph, and returns the index of this new edge
	 * if this edge already exists, weight is added to the existing edge and it's index is returned
	 * @param e
	 * the kGraphEdge to add
	 */
	public int appendEdge(kLine l, int weight) {
		int si = nodes.append(l.StartPoint());
		int ei = nodes.append(l.EndPoint());
		return appendEdge(new kGraphEdge(si,ei,weight));
	}	
	
	public void removeNode(int index){
		IndexList hitList = new IndexList();
		for (int e = 0; e < edges.length; e++) {
			if ((edges[e].si==index)||(edges[e].ei==index)){
				hitList.append(e);
			}	
			edges[e].indexDownIfGreater(index);
		}
		for (int i = 0; i < hitList.count(); i++) {
			removeEdge(hitList.getAt(i),true);	
		}
		nodes.removeAt(index);
	}
	
	/**
	 * removes an edge at a given index
	 * @param e
	 * the kGraphEdge to add
	 */	
	public void removeEdge(int indexToRemove, boolean preserveNodes){
		//TODO: cull unused nodes
		kGraphEdge[] temp = this.edges;
		int n = 0;
		this.edges = new kGraphEdge[this.edges.length];
		for (int i = 0; i < temp.length; i++) {
			if (i!=indexToRemove){
				this.edges[n] = temp[i];
				n=n+1;
			}
		}
	}
	
	public void removeEdges(int[] indicesToRemove, boolean preserveNodes){
		//TODO: cull unused nodes
		kGraphEdge[] temp = this.edges;
		int n = 0;
		this.edges = new kGraphEdge[this.edges.length-indicesToRemove.length];
		for (int i = 0; i < temp.length; i++) {
			boolean removeIt = false;
			for (int j = 0; j < indicesToRemove.length; j++) {
				if (i==indicesToRemove[j]){removeIt = true;}
			}
			if (!removeIt){
				this.edges[n] = temp[i];
				n=n+1;
			}
		}
	}	

	
	/**
	 * checks if a given kGraphEdge already exists within this graph, and returns this index
	 * (performs check based on index, not point location)
	 * @param e
	 * the kGraphEdge to check
	 */	
	public int indexOfExistingEdge(kGraphEdge e) {
		for (int i = 0; i < edges.length; i++) {
			if (edges[i].isIdentical(e)) return i;
		}
		return -1;
	}

	public kVec getNode(int index) {
		return nodes.getAt(index);
	}

	public kLine edgeLine(int index){
		return new kLine(nodes.getAt(edges[index].si),nodes.getAt(edges[index].ei));
	}
	
	/*
	 * IO
	 * 
	 * 
	 * 
	 */

	public boolean parseDataString(String[] dataString) {
		//TODO: formalize kGraph.parseDataString better
		
		for (int i = 0; i < dataString.length; i++) {
			String str = dataString[i];
			if (str.indexOf("node") >= 0) {
				str = str.substring(str.indexOf("<") + 1, str.indexOf(">"));
				String[] posStr = str.split(",");

				kVec vec = new kVec(kUtil.toFloat(posStr[0]), kUtil.toFloat(posStr[1]), kUtil.toFloat(posStr[2]));
				this.appendNode(vec);
				// println ("nodeat ("+vec.x+","+vec.y+","+vec.z+")");
			} else if (str.indexOf("edge") >= 0) {
				String[] edgeArr = str.split(" ");
				// 1
				int st = edgeArr[1].indexOf("<");
				int ed = edgeArr[1].indexOf(">");
				edgeArr[1] = edgeArr[1].substring(st + 1, ed);
				String[] lnkStr = edgeArr[1].split(",");
				int startIndex = kUtil.toInt(lnkStr[0].trim());
				int endIndex = kUtil.toInt(lnkStr[1].trim());
				// 2
				int weight = kUtil.toInt(edgeArr[2]);

				this.appendEdge(new kGraphEdge(startIndex, endIndex, weight));

				// print("edgeat("+pnt[0]+","+pnt[1]+" ["+weight+"])");
			} else {
				System.out.println("kGraph parseDataString error: line " + i);
			}
		}
		return true;
	}

	/*
	 * MANIPULATION
	 * 
	 * 
	 * 
	 */

	
	public void merge(kGraph g) {
		kGraphEdge[] newEdges = g.edges;
		for (int n = 0; n < g.nodes.count(); n++) {
			int index = appendNode(g.getNode(n));
			for (int e = 0; e < newEdges.length; e++) {
				if (newEdges[e].si == n) {
					newEdges[e].si = -index;
				}
				if (newEdges[e].ei == n) {
					newEdges[e].ei = -index;
				}
			}
		}
		for (int e = 0; e < newEdges.length; e++) {
			appendEdge(new kGraphEdge(-newEdges[e].si, -newEdges[e].ei, newEdges[e].w));
		}
		
		cleanup();
	}
	
	public void cleanup(){
		maximizeOverlappedEdges();
		maximizeEmbeddedEdges();
		divideEdgesAtIntersectingNodes();
		removeUnusedNodes();
	}
	
	private void maximizeEmbeddedEdges(){
		int e = 0;
		while (e<edges.length){
			for (int f = 0; f < edges.length; f++) {
				if (e!=f){
					kLine lf = edgeLine(f);
					kLine le = edgeLine(e);
					if (le.isEmbedded(lf)){
						//System.out.println("found embedded ["+e+","+f+"]");
						if (le.vec.angle(lf.vec) > Math.PI/2){
							//lines pointing opposite directions
							appendEdge(new kGraphEdge(edges[e].si, edges[f].ei, edges[e].w));
							appendEdge(new kGraphEdge(edges[f].si, edges[e].ei, edges[e].w));
						} else {
							//lines pointing same direction
							appendEdge(new kGraphEdge(edges[e].si, edges[f].si, edges[e].w));
							appendEdge(new kGraphEdge(edges[f].ei, edges[e].ei, edges[e].w));
						}
						edges[f].gainWeight(edges[e].w);
						removeEdges(new int[]{e}, true);
						e--;
						break;
					}
				}
			}
			e++;
		}
	}
	
	private void maximizeOverlappedEdges(){
		int e = 0;
		while (e<edges.length){
			for (int f = 0; f < edges.length; f++) {
				if (e!=f){
					kLine lf = edgeLine(f);
					kLine le = edgeLine(e);
					kLine lo = lf.overlappingSegment(le, true);
					if ( (lo.isValid)&&(!lf.isEmbedded(le))&&(!le.isEmbedded(lf)) ){
						//System.out.println("found overlapped: ["+e+","+f+"]"+le.vec.angle(lf.vec)+"_"+lo.length());
						appendEdge(lf.overlappingSegment(le, true),edges[e].w+edges[f].w);
						appendEdge(lf.overlappingSegment(le, false),edges[f].w);
						appendEdge(le.overlappingSegment(lf, false),edges[e].w);
						
						//System.out.println(lf.overlappingSegment(le, true).toString());
						//System.out.println(lf.overlappingSegment(le, false).toString());
						//System.out.println(le.overlappingSegment(lf, false).toString());
						//edges[f].gainWeight(edges[e].w);
						removeEdges(new int[]{e,f}, true);
						e = -1;
						break;
					}
				}
			}
			e++;
		}
	}
	
	private void divideEdgesAtIntersectingNodes() {
		IndexList hitList = new IndexList();
		for (int e = 0; e < edges.length; e++) {
			kLine eLine = edgeLine(e);
			kPointCloud divisors = new kPointCloud();
			for (int n = 0; n < nodes.count(); n++) {
				if ((n != edges[e].si) && (n != edges[e].ei)) {
					kVec nPt = getNode(n);
					if (eLine.distanceTo(nPt) < kElement.tolerence) {
						//System.out.println("found node "+n+" on edge "+e);
						if ((eLine.StartPoint().distance(nPt) != 0.0f)&& (eLine.EndPoint().distance(nPt) != 0.0f) ){
							divisors.append(nPt);
						}
					}
				}
			}
			if (divisors.count() > 0) {
				int c = 0;
				kVec div = eLine.StartPoint();
				while (divisors.count() > 0) {
					//System.out.println("divisors.count:" + divisors.count());
					int i = divisors.getIndexOfNearestPoint(eLine.StartPoint(), false);
					appendEdge(new kLine(div,divisors.getAt(i)),edges[e].w);
					div = divisors.getAt(i);
					divisors.removeAt(i);
					c++;
					if (c > 50) {
						break;
					}
				}
				appendEdge(new kLine(div,eLine.EndPoint()),edges[e].w);
				hitList.append(e);
			}
		}
		removeEdges(hitList.toArray(), true);
	}
	
	public void removeUnusedNodes(){
		for (int n = 0; n < nodes.count(); n++) {
			boolean remove = true;
			for (int e = 0; e < edges.length; e++) {
				if ((edges[e].si == n)||(edges[e].ei == n)){
					remove = false;
					break;
				}
			}
			if (remove){
				removeNode(n);
				n--;
			}
		}

	}

	public kVec centroid() {
		return kVec.centroid(nodes.getPts());
	}

	public void scale(float s) {
		nodes.scale(s);
	}

	public void translate(kVec vec) {
		nodes.translate(vec);
	}

	public String toString() {
		String str = this.nodes.count() + " nodes, " + this.edges.length + " edges\n";
		for (int i = 0; i < edges.length; i++) {
			str+="["+edges[i].si+","+edges[i].ei+"]";
		}	
		return str;
	}
}
